package com.company.堆栈队列;

import java.util.ArrayList;
import java.util.PriorityQueue;

/**
 * @author Administrator
 * <p>
 * 使用数据结构 ---->大根堆
 */
public class 最小的K个数 {
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        if (input.length == 0 || k == 0) {
            return res;
        }
        // 大根堆,PriorityQueue默认是小跟堆，
        // 1.大根堆需要重新写比较器，
        // 2.可以在 new PriorityQueue<>() 中的参数部分加入比较器。
        //3.具体写法是：(v1, v2) -> v2 - v1。
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2.compareTo(o1));
        // 构建一个大小为k的堆
        for (int i = 0; i < k; i++) {
            queue.offer(input[i]);
        }
        for (int i = k; i < input.length; i++) {
            //较小元素入堆
            if (queue.peek() > input[i]) {
                queue.poll();
                queue.offer(input[i]);
            }
        }
        //堆中元素取出入数组
        for (int i = 0; i < k; i++) {
            res.add(queue.poll());
        }
        return res;
    }

    public static void main(String[] args) {
        最小的K个数 min = new 最小的K个数();
        int[] array = {4, 5, 1, 6, 2, 7, 3, 8};
        int k = 4;
        ArrayList<Integer> integers = min.GetLeastNumbers_Solution(array, k);
        System.out.println(integers);
    }
}
